70. 爬楼梯

Similar Question

这道题目还可以继续深化，就是一步一个台阶，两个台阶，三个台阶，直到 m 个台阶，有多少种方法爬到 n 阶楼顶。

这又有难度了，这其实是一个完全背包问题，但力扣上没有这种题目，所以后续我在讲解背包问题的时候，今天这道题还会从背包问题的角度上来再讲一遍。 如果想提前看一下，可以看这篇:70.爬楼梯完全背包版本

此时我就发现一个绝佳的大厂面试题，第一道题就是单纯的爬楼梯，然后看候选人的代码实现，如果把 dp[0] 的定义成 1 了，就可以发难了，为什么 dp[0] 一定要初始化为 1，此时可能候选人就要强行给 dp[0] 应该是 1 找各种理由。那这就是一个考察点了，对 dp[i] 的定义理解的不深入。

然后可以继续发难，如果一步一个台阶，两个台阶，三个台阶，直到 m 个台阶，有多少种方法爬到 n 阶楼顶。这道题目 leetcode 上并没有原题，绝对是考察候选人算法能力的绝佳好题。

这一连套问下来，候选人算法能力如何，面试官心里就有数了。

Solution Tips

方案一: 备忘录方法

分析递归的方法我们可以发现，其实有很多的计算过程其实是重复的，因此我们可以使用一个数组，将已经计算出的值给 保存下来，每次计算时，先判断计算结果是否已经存在，如果已经存在就直接使用。

let map = new Map();

function getClimbingWays(n) {

  if (n < 1) {
    return 0;
  }

  if (n === 1) {
    return 1;
  }

  if (n === 2) {
    return 2;
  }

  if (map.has(n)) {
    return map.get(n);
  } else {
    let value = getClimbingWays(n - 1) + getClimbingWays(n - 2);
    map.set(n, value);
    return value;
  }
}

通过这种方式，我们将算法的时间复杂度降低为 O(n)，但是增加空间复杂度为 O(n)

方案二: 斐波那契数列 + Dp

从递归 +memo 出发, 寻找 dp 规律

var climbStairs = function(n) {
    if (n <= 2) return n;
    let prevPrev = 1;
    let prev = 2;
    let cur;
    // 从 3 开始
    for (let i = 3; i <= n; i++) {
        cur = prev + prevPrev;
        prevPrev = prev;
        prev = cur;
    }

    return cur;
};